//Given a binary tree and a sum,
//determine if the tree has a root-to-leaf path such that
//adding up all the values along the path equals the given sum.
//Given the below binary tree and sum = 22, return true;
//		     5
//          / \
//        4   8
//        /   / \
//       11  13  4
//      /  \      \
//     7    2      1



class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
         if(root == NULL)return false;
    	 if(root->left ==NULL && root->right == NULL){
    		 if(root->val == sum)
    			 return true;
    		 else
    			 return false;
    	 }

    	 return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }

};



//Main function is for test. 
int main(){
	Solution sol;
	TreeNode root(5);
	TreeNode node4(4),  node8(8), node11(11),node13(13),node42(4),node7(7),node2(2),node1(1);
	root.left = &node4;
	root.right = &node8;
	node4.left = &node11;
	node11.left = &node7;
	node11.right = &node2;
	node8.left = &node13;
	node8.right = &node42;
	node42.right =&node1;


	fprintf(stdout,"%d ",sol.hasPathSum(&root,22));


}
